package com.interview.javabase.algorithm;

/**
 * @description:
 * @author: zhangshuguang@vichain.com
 * @date: 2019/09/29 10:53
 */
public class AVLTree {

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();
        int[] arr = {1, 9, 5, 6, 5, 2, 3, 6, 58, 7, 4};
        for (int i = 0; i < arr.length; i++) {
            int i1 = arr[i];
            avlTree.add(new AVLTreeNode(i1));
        }

        avlTree.infixOrder();
        int height = avlTree.root.height();
        System.out.println(height);

    }

    private AVLTreeNode root;

    public void add(AVLTreeNode AVLTreeNode) {
        if (this.root == null) {
            this.root = AVLTreeNode;
        } else {
            this.root.add(AVLTreeNode);
        }
    }

    public AVLTreeNode findAVLTreeNode(AVLTreeNode AVLTreeNode) {
        if (this.root != null) {
            return this.root.findAVLTreeNode(AVLTreeNode);
        }

        return null;
    }

    public void deleteAVLTreeNode(AVLTreeNode targetNode) {

        if (root.left == null && root.right == null) {
            root = null;
            return;
        }

        if (targetNode == null) {
            return;
        }

        // 查找需要删除的子树
        AVLTreeNode AVLTreeNode = this.findAVLTreeNode(targetNode);
        if (AVLTreeNode == null) {
            System.out.println("查找的数据不存在");
            return;
        }

        AVLTreeNode AVLTreeNodeParent = this.root.findAVLTreeNodeParent(targetNode);

        // 1. 删除的节点为叶子节点
        if (AVLTreeNode.right == null && AVLTreeNode.left == null) {
            if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                AVLTreeNodeParent.left = null;
            } else {
                AVLTreeNodeParent.right = null;
            }

        } else if (AVLTreeNode.right == null || AVLTreeNode.left == null) {
            // 2. 删除的节点有一颗子树
            if (AVLTreeNode.right != null) {
                if (AVLTreeNodeParent == null) {
                    root = AVLTreeNode.right;
                } else if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                    AVLTreeNodeParent.left = AVLTreeNode.right;
                } else {
                    AVLTreeNodeParent.right = AVLTreeNode.right;
                }
            } else {
                if (AVLTreeNodeParent == null) {
                    root = AVLTreeNode.left;
                } else if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                    AVLTreeNodeParent.left = AVLTreeNode.left;
                } else {
                    AVLTreeNodeParent.right = AVLTreeNode.left;
                }
            }
        } else {
            // 3. 删除的节点有两颗子树
            // 查找右子树最小的节点
            AVLTreeNode minAVLTreeNode = AVLTreeNode.right.findMinAVLTreeNode();
            AVLTreeNode.value = minAVLTreeNode.value;
        }
    }

    public AVLTreeNode findParentAVLTreeNode(AVLTreeNode AVLTreeNode) {
        if (this.root != null) {
            return this.root.findAVLTreeNodeParent(AVLTreeNode);
        }

        return null;
    }

    // 查询最小的节点
    public AVLTreeNode findMinAVLTreeNode(AVLTreeNode AVLTreeNode) {

        return AVLTreeNode.right.findMinAVLTreeNode();
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        }
    }
}

class AVLTreeNode {
    int value;
    AVLTreeNode left;
    AVLTreeNode right;

    public AVLTreeNode(int value) {
        this.value = value;
    }

    public int height() {
        return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;
    }

    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("AVLTreeNode{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }

    public void deleteNode(AVLTreeNode targetNode) {
        if (targetNode == null) {
            return;
        }

        // 查找需要删除的子树
        AVLTreeNode AVLTreeNode = this.findAVLTreeNode(targetNode);
        if (AVLTreeNode == null) {
            System.out.println("查找的数据不存在");
            return;
        }

        AVLTreeNode AVLTreeNodeParent = this.findAVLTreeNodeParent(targetNode);

        // 1. 删除的节点为叶子节点
        if (AVLTreeNode.right == null && AVLTreeNode.left == null) {
            if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                AVLTreeNodeParent.left = null;
            } else {
                AVLTreeNodeParent.right = null;
            }

        } else if (AVLTreeNode.right == null || AVLTreeNode.left == null) {
            // 2. 删除的节点有一颗子树
            if (AVLTreeNode.right != null) {
                if (AVLTreeNodeParent == null) {
                    AVLTreeNode root = this;
                    root = AVLTreeNode.right;
                } else if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                    AVLTreeNodeParent.left = AVLTreeNode.right;
                } else {
                    AVLTreeNodeParent.right = AVLTreeNode.right;
                }
            } else {
                if (AVLTreeNodeParent == null) {
                    AVLTreeNode root = this;
                    root = AVLTreeNode.left;
                } else if (AVLTreeNodeParent.left != null && AVLTreeNodeParent.left == AVLTreeNode) {
                    AVLTreeNodeParent.left = AVLTreeNode.left;
                } else {
                    AVLTreeNodeParent.right = AVLTreeNode.left;
                }
            }
        } else {
            // 3. 删除的节点有两颗子树
            // 查找右子树最小的节点
            AVLTreeNode minAVLTreeNode = AVLTreeNode.right.findMinAVLTreeNode();
            AVLTreeNode.value = minAVLTreeNode.value;
        }
    }

    // 查询最小的节点
    public AVLTreeNode findMinAVLTreeNode() {

        if (this.left == null) {
            deleteNode(this);
            return this;
        }

        return this.left.findMinAVLTreeNode();
    }

    /**
     * 添加节点
     * @param AVLTreeNode
     */
    public void add(AVLTreeNode AVLTreeNode) {

        if (AVLTreeNode == null) {
            return;
        }

        if (AVLTreeNode.value < this.value) {
            if (this.left == null) {
                this.left = AVLTreeNode;
            } else {
                this.left.add(AVLTreeNode);
            }
        } else {
            if (this.right == null) {
                this.right = AVLTreeNode;
            } else {
                this.right.add(AVLTreeNode);
            }
        }

        // 左旋
        if (rightHeight() - leftHeight() > 1){
            // 如果存在当前节点右子树的左子树的高度大于当前节点的右子树的右子树的高度
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()){
                this.right.rightRotate();
                this.leftRotate();
            } else {
                this.leftRotate();
            }
            return;
        }

        // 右旋
        if (leftHeight() - rightHeight() > 1){
            // 如果存在当前节点左子树的右子树的高度大于当前节点的左子树的左子树的高度
            if (this.right != null && this.right.leftHeight() > this.right.rightHeight()){
                this.left.leftRotate();
                this.rightHeight();
            } else {
                this.rightHeight();
            }
            return;
        }

    }

    /**
     * 查找值
     */
    public AVLTreeNode findAVLTreeNode(AVLTreeNode AVLTreeNode) {

        if (AVLTreeNode == null) {
            return null;
        }

        if (AVLTreeNode.value < this.value) {
            return this.left.findAVLTreeNode(AVLTreeNode);
        }

        if (AVLTreeNode.value > this.value) {
            return this.right.findAVLTreeNode(AVLTreeNode);
        }

        if (this.value == AVLTreeNode.value) {
            return this;
        }

        return null;
    }

    /**
     * 查找值
     */
    public AVLTreeNode findAVLTreeNodeParent(AVLTreeNode AVLTreeNode) {

        if ((this.left != null && this.left.value == AVLTreeNode.value) || this.right != null && this.right.value == AVLTreeNode.value) {
            return this;
        } else {
            if (this.left != null) {
                return this.left.findAVLTreeNodeParent(AVLTreeNode);
            } else if (this.right != null) {
                return this.right.findAVLTreeNodeParent(AVLTreeNode);
            } else {
                return null;
            }
        }

    }

    public int leftHeight(){
        if (left == null){
            return 0;
        }

        return this.left.height();
    }

    public int rightHeight(){
        if (right == null){
            return 0;
        }

        return this.right.height();
    }

    public void leftRotate(){
        AVLTreeNode avlTreeNode = new AVLTreeNode(value);
        avlTreeNode.left = this.left;
        avlTreeNode.right = this.right.left;
        this.value = this.right.value;
        this.left = avlTreeNode;
        this.right = this.right.right;
    }

    public void rightRotate(){
        AVLTreeNode avlTreeNode = new AVLTreeNode(value);
        avlTreeNode.right = this.right;
        avlTreeNode.right = this.left.right;
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = avlTreeNode;
    }


    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }

        System.out.println(this);

        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}
